#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <cstdio>
using namespace std;
using ll=long long;
const int N=1e5+10;

int n,k;

vector<pair<int,int>> edge[N];
ll dist[N];
int cnt[N];
bool st[N];
bool spfa()
{
	memset(dist,-0x3f,sizeof(dist));
	memset(cnt,0,sizeof(cnt));
	st[0]=true;
	dist[0]=0;
	stack<int> s;
	s.push(0);
	while(s.size())
	{
		int t=s.top();
		st[t]=false;
		s.pop();

		for(auto& e:edge[t])
		{
			if(dist[e.first]<dist[t]+e.second)
			{
				dist[e.first]=dist[t]+e.second;
				cnt[e.first]=cnt[t]+1;
				if(cnt[e.first]>=n+1)
					return false;
				if(!st[e.first])
				{
					s.push(e.first);
					st[e.first]=true;
				}
			}
		}
	}
	return true;
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<k;i++)
	{
		int x,a,b;
		scanf("%d%d%d",&x,&a,&b);
		
		if(x==1)
		{
			edge[a].push_back({b,0});
			edge[b].push_back({a,0});
		}
		else if(x==2)
		{
			edge[a].push_back({b,1});
		}
		else if(x==3)
		{
			edge[b].push_back({a,0});
		}
		else if(x==4)
		{
			edge[b].push_back({a,1});
		}
		else{
			edge[a].push_back({b,0});
		}	
	}
	for(int i=1;i<=n;i++)
	{
		edge[0].push_back({i,1});
	}
	if(!spfa())
		cout<<-1<<endl;
	else{
		ll ret=0;
		for(int i=1;i<=n;i++)
			ret+=dist[i];
		cout<<ret<<endl;
	}
	return 0;
}
